package com.leetcode.程序员面试金典.medium;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author 覃国强
 * @date 2021-04-20 12:39
 */
public class 面试题_17_18_最短超串 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[] big = {7, 5, 0, 2, 3, 5, 7, 9};
    int[] small = {1, 5, 9};
    int[] seq = solution.shortestSeq(big, small);
    System.out.println(Arrays.toString(seq));
  }

  static
  class Solution {

    public int[] shortestSeq(int[] big, int[] small) {
      Map<Integer, Integer> map = new HashMap<>(small.length * 3 / 2);
      for (int num : small) {
        map.put(num, 0);
      }
      int len = 0;

      int minLen = Integer.MAX_VALUE;
      int[] result = new int[2];

      int left = 0;
      int right = 0;

      while (left <= right && right <= big.length) {
        if (len == small.length) {
          // 找到一个符合条件的子序列，移动 left 指针
          int tmpMinLen = right - left;
          if (tmpMinLen < minLen) {
            minLen = tmpMinLen;
            result[0] = left;
            result[1] = right - 1;
          }
          len = moveLeft(left, big, map, len);
          ++left;
        } else if (right < big.length) {
          // 没有找到符合条件的子序列，移动 right 指针
          len = moveRight(right, big, map, len);
          ++right;
        } else {
          // 没有找到符合条件的子序列，而且 right 指针已经到末尾
          break;
        }
      }

      if (minLen == Integer.MAX_VALUE) {
        return new int[0];
      }

      return result;
    }

    private int moveRight(int right, int[] big, Map<Integer, Integer> map, int len) {
      if (map.containsKey(big[right])) {
        int count = map.get(big[right]);
        if (count == 0) {
          ++len;
        }
        map.put(big[right], count + 1);
      }
      return len;
    }

    private int moveLeft(int left, int[] big, Map<Integer, Integer> map, int len) {
      if (map.containsKey(big[left])) {
        int count = map.get(big[left]);
        if (count == 1) {
          --len;
        }
        map.put(big[left], count - 1);
      }
      return len;
    }
  }

}
